Choice function

 ( Basic Concepts In Set Theory ) 

Let X be a set of sets none of which are empty. Then a choice function ( selector, selection) on X is a mathematical function f that is defined on X such that f is a mapping that assigns each element of X to one of its elements.

---

An example Let X = { {1,4,7}, {9}, {2,7} }. Then the function f defined by f({1, 4, 7}) = 7, f({9}) = 9 and f({2, 7}) = 2 is a choice function on X.

---

History and importance Ernst Zermelo (1904) introduced choice functions as well as the axiom of choice (AC) and proved the well-ordering theorem, which states that every set can be well ordering. AC states that every set of nonempty sets has a choice function. A weaker form of AC, the axiom of countable choice (AC_ω) states that every countable set of nonempty sets has a choice function. However, in the absence of either AC or AC_ω, some sets can still be shown to have a choice function.

• If $X$ is a finite set set of nonempty sets, then one can construct a choice function for $X$ by picking one element from each member of $X.$ This requires only finitely many choices, so neither AC or AC_ω is needed.
• If every member of $X$ is a nonempty set, and the union $\backslash bigcup\; X$ is well-ordered, then one may choose the least element of each member of $X$. In this case, it was possible to simultaneously well-order every member of $X$ by making just one choice of a well-order of the union, so neither AC nor AC_ω was needed. (This example shows that the well-ordering theorem implies AC. The converse is also true, but less trivial.)

---

Choice function of a multivalued map Given two sets $X$ and $Y$, let $F$ be a multivalued map from $X$ to $Y$ (equivalently, $F:X\backslash rightarrow\backslash mathcal\{P\}(Y)$ is a function from $X$ to the power set of $Y$).

A function $f:\; X\; \backslash rightarrow\; Y$ is said to be a selection of $F$, if:

$$\backslash forall\; x\; \backslash in\; X\; \backslash ,\; (\; f(x)\; \backslash in\; F(x)\; )\; \backslash ,.$$

The existence of more regular choice functions, namely continuous or measurable selections is important in the theory of differential inclusions, optimal control, and mathematical economics.

See Selection theorem.

---

Bourbaki tau function Nicolas Bourbaki used epsilon calculus for their foundations that had a $\backslash tau$ symbol that could be interpreted as choosing an object (if one existed) that satisfies a given proposition. So if $P(x)$ is a predicate, then $\backslash tau\_\{x\}(P)$ is one particular object that satisfies $P$ (if one exists, otherwise it returns an arbitrary object). Hence we may obtain quantifiers from the choice function, for example $P(\; \backslash tau\_\{x\}(P))$ was equivalent to $(\backslash exists\; x)(P(x))$.

Nicolas Bourbaki (1968). 9780201006346, Hermann. ISBN 9780201006346

However, Bourbaki's choice operator is stronger than usual: it's a global choice operator. That is, it implies the axiom of global choice.John Harrison, "The Bourbaki View" eprint. Hilbert realized this when introducing epsilon calculus."Here, moreover, we come upon a very remarkable circumstance, namely, that all of these transfinite axioms are derivable from a single axiom, one that also contains the core of one of the most attacked axioms in the literature of mathematics, namely, the axiom of choice: $A(a)\backslash to\; A(\backslash varepsilon(A))$, where $\backslash varepsilon$ is the transfinite logical choice function." Hilbert (1925), “On the Infinite”, excerpted in Jean van Heijenoort, From Frege to Gödel, p. 382. From nCatLab.

---

See also

• Axiom of countable choice
• Axiom of dependent choice
• Hausdorff paradox
• Hemicontinuity

---

Notes

Post Comment